package main

import "fmt"

func shellSortStep(arr []int, start int, gap int) []int {
	// 数组长度
	length := len(arr)
	// 插入排序的变种
	for i := start + gap; i < length; i += gap {
		// 备份待插入的数据
		backup := arr[i]
		// 初始化待插入位置
		j := i - gap
		// 待插入数据，小于前面的数据
		for j >= 0 && backup < arr[j] {
			// 从前往后移动
			arr[j+gap] = arr[j]
			j -= gap
		}
		arr[j+gap] = backup
	}
	return arr
}

func ShellSort(arr []int) []int {
	// 数组长度
	length := len(arr)
	// 数组为空或者只有一个元素
	if length <= 1 {
		return arr
	}
	// 步长
	//Kunth序列
	gap := 1
	for gap <= length/3 {
		gap = gap*3 + 1
	}
	for gap > 0 {
		// 处理每个元素的步长
		for i := 0; i < gap; i++ {
			shellSortStep(arr, i, gap)
		}
		gap = (gap - 1) / 3
	}
	return arr
}

func main() {
	arr := []int{2, 1, 5, 6, 3, 4}
	fmt.Println(ShellSort(arr))

}
